package com.lichong;

/**
 * @program: 左程云算法
 * @description
 * @author: LiChong
 * @create: 2021-05-07 16:31
 **/
public class Code03_list {
    static   class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        groupByK(node1,2);
    }
    /**
     *给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储一位数字。
     *请你将两个数相加，并以相同形式返回一个表示和的链表。
     *你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *每个链表中的节点数在范围 [1, 100] 内
     *0 <= Node.val <= 9
     *题目数据保证列表表示的数字不含前导零
     * eg:输入：l1 = [2,4,3], l2 = [5,6,4]
     * 输出：   [7,0,8]
     * 解释：  342 + 465 = 807.
     */
    public static ListNode  addList(ListNode head1,ListNode head2){
        if (head1==null||head2==null){
            return null;
        }
        ListNode longNode = null;
        ListNode shortNode = null;
        ListNode head1Copy = head1;
        ListNode head2Copy = head2;
        ListNode res = null;
        ListNode pre = null;
        int count1=0,count2=0;
        while(head1!=null){
            head1 = head1.next;
            count1++;
        }
        while(head2!=null){
            head2 = head2.next;
            count2++;
        }
        int carry = 0;
        longNode = count1>count2?head1Copy:head2Copy;
        shortNode = count1>count2?head2Copy:head1Copy;
        res = longNode;
        while(shortNode!=null){
            int value=shortNode.val+longNode.val+carry;
            carry = value>=10 ? 1 :0;
            int addVal = value % 10;
            longNode.val =addVal;
            if (longNode.next==null&&carry==1){
                pre = longNode;
            }
            longNode = longNode.next;
            shortNode = shortNode.next;
        }
        while (longNode!=null&&carry==1){
            int longVal = longNode.val+carry;
            longNode.val = longVal%10;
            carry = longVal>=10 ? 1 :0;
            if (longNode.next==null&&carry==1){
               pre = longNode;
            }
            longNode = longNode.next;
        }
        if (pre!=null){
            pre.next = new ListNode(1);
        }
        return res;
    }

    /**
     * k个一组反转链表
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 进阶：
     *     你可以设计一个只使用常数额外空间的算法来解决此问题吗？
     *     你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode  groupByK(ListNode head , int k){
        ListNode last = null;
        ListNode tailBeforeR = null;
        ListNode tailAfterR = null;
        ListNode cur = null;
        ListNode res = head;
        ListNode first = head;
        ListNode end = null;
        while(head!=null){
            if(isSatisfiedGroupRule(head,k)){
                tailBeforeR =  findTailBeforeReverse(head, k);
                end = tailBeforeR.next;
                 cur = reverseList(head,tailBeforeR);
                 tailAfterR = findTailAfterReverse(cur,k);
                if (last!=null){
                    last.next = cur;
                }
                last = findTailAfterReverse(cur,k);
                if (tailAfterR==first){
                    res = cur;
                }
            }else {
                if (last!=null){
                    last.next = head;
                    break;
                }
            }
            head = end;

        }
        return res;

    }
    public static ListNode reverseList(ListNode head,ListNode tail){
        if (head==null||tail==null){
            return null;
        }
        ListNode pre = null;
        ListNode next = null;
        ListNode tailCopy = tail.next;
        while (head!=null&&head!=tailCopy){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    public static ListNode findTailAfterReverse(ListNode head,int k ){
        if (head==null||k==0){
            return  null;
        }
        for (int i = 1; i < k; i++) {
            head = head.next;
        }
        return head;
    }
    public static boolean isSatisfiedGroupRule(ListNode head,int k){
        if (head==null||k==0){
            return false;
        }
        for (int i = 1; i <k ; i++) {
            head = head.next;
            if (head==null){
                return false;
            }
        }
        return true;
    }
    public static ListNode findTailBeforeReverse(ListNode head,int k){
        if (head==null||k==0){
            return  null;
        }
        for (int i = 1; i < k; i++) {
            head = head.next;
        }
        return head;
    }
}
